package com.lh.jianzhioffer.专项练习.字符串;

/**
 * @author: linghao
 * @since: 2023/3/4
 *
 * 给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串
 *
 * 贪心
 */
public class 最多删除一个字符得到回文019 {

    public boolean validPalindrome(String s) {
        int low=0,high=s.length()-1;
        while (low<high){
            char c1 = s.charAt(low),c2 = s.charAt(high);
            if(c1 == c2){
                low++;
                high--;
            }else{
                //高位或低位任一删除一个判断剩余
                return validPalindrome(s,low+1,high)||validPalindrome(s,low,high-1);
            }
        }
        return true;
    }

    private boolean validPalindrome(String s, int low, int high) {
        for(int i=low,j=high;i<j;i++,j--){
            char c1 = s.charAt(i),c2 = s.charAt(j);
            if(c1 != c2)return false;
        }
        return true;
    }
}
